1. Field of the Invention
The present invention relates in general to two network protocols which are particularly suitable for self-reconfigurable communications networks, such as ad-hoc networks. More particularly, the first protocol is instrumental in efficiently finding routes within a network, while the second protocol can be used to locate users in a network with rapidly changing topology.
2. Background Information and Description of the Prior Art
A. The Notion of the Ad-Hoc Network
An ad-hoc network architecture is a network that can be deployed rapidly and without relying on preexising fixed network infrastructure. The nodes in an ad-hoc network can dynamically join and leave the network, frequently, often without warning, and without disruption to other nodes' communication. Finally, the nodes in the network can be highly mobile, thus rapidly changing the node constellation and the presence or absence of links. Examples of the use of the ad-hoc networks are:
tactical operation--for fast establishment of communication infrastructure during force deployment in unknown and hostile terrain;
rescue missions--for communication in areas without adequate wireless coverage; PA1 national security--for communication in times of national crisis, where the existing communication infrastructure is non-operational due to a natural disaster or a global war; PA1 law enforcement--for fast establishment of communication infrastructure during law enforcement operations; PA1 commercial use--for setting up communication in exhibitions, conferences, or sale presentations; PA1 education--for operation of wall-free (virtual) classrooms; and PA1 sensor networks--for communication between intelligent sensors (e.g., MEMS) mounted on mobile platforms. PA1 the network should be immediately deployable (and re-deployable) in unknown, arbitrary communication environments; PA1 radio propagation conditions can differ vastly throughout the network coverage and can constantly change; PA1 connectivity between adjacent nodes can be intermittent and sporadic, both due to the nodal mobility and due to propagation conditions; and PA1 there may not be any fixed infrastructure present; the mobile nodes are all the elements of the network. PA1 the lack of a centralized entity; PA1 the possibility of rapid platform movements; and PA1 the fact that all communication is carried over the wireless medium. PA1 Robust routing and mobility management algorithms to increase the networks reliability, survivability and availability; i.e., any remaining network components should operate even in the case that a large portion of the network is wiped out, partitioned, or incapacitated; PA1 Adaptive algorithms and protocols to adjust to frequently changing radio propagation, network, and traffic conditions; PA1 Low-overhead algorithms and protocols to preserve the radio communication resource; PA1 Multiple (distinct) routes between a source and a destination--to reduce the congestion in the vicinity of certain nodes, and to increase the reliability and survivability; and PA1 Non-hierarchical physical network architecture to avoid the susceptibility to network failures, congestion around certain nodes, and the penalty due to inefficient routing.
Nodes in an ad-hoc network exhibit nomadic behavior by freely migrating within some area, and dynamically creating and tearing down associations with other nodes. Groups of nodes that have a common goal can create formations (clusters) and migrate together, similarly to military units on missions. Nodes can communicate with each other at anytime and without restrictions, except for connectivity limitations and subject to security provisions. For example, in military applications, the network nodes can represent soldiers, trucks, tanks, planes helicopters, ships or unmanned robots.
Some of the distinctive attributes of ad-hoc networks are:
B. The Challenges of the Ad-Hoc Networks and Previous Work
The topic of ad-hoc networking has received increased attention recently. This interest comes from two different directions--from the military and from the Internet community. Of course, as the communication and networking environment of these two "markets" is quite different, the requirements, and more important the expectations, of what this technology can accomplish are quite different as well.
The three main challenges in the design and operation of the ad-hoc networks stem from
In "regular" cellular wireless networks, there are a number of centralized entities; e.g., the base stations, the Mobile Switching Centers (MSC-s), and the Home Location Registry. In ad-hoc networks, since there is no preexisting infrastructure, these centralized entities do not exist. The centralized entities in the cellular networks perform the function of coordination. Thus, lack of these entities in the ad-hoc networks requires more sophisticated distributed algorithms to perform these functions. In particular, the traditional algorithms for mobility management, which rely on the HLR/VLR (Home Location Register/Visitor Location Register) and the medium access control schemes, including the channel assignment procedures, which rely on the base-station/MSC (Mobile Switching Center) support, cannot be used here.
All communications between all network entities are carried in ad-hoc networks over the wireless medium Of course, due to the radio communications being extremely vulnerable to propagation impairments, connectivity between network nodes is not guaranteed. In fact intermittent and sporadic connectivity may be quite common. Additionally, as the wireless bandwidth is limited, its use should be minimized. Finally, as some of the mobile devices are expected to be hand-held with limited power sources, the required transmission power should be minimized as well The last two attributes, conservation of wireless spectrum and reduction in transmission power, lead naturally to an architecture in which the transmission radius of each mobile is limited and channels assigned to mobiles are spatially reused. Consequently, since the transmission radius is much smaller than the network span, communication between two terminals may need to be relayed through intermediate nodes; i.e., multi-hop routing.
Because of the possibly rapid movement of the nodes and fast changing propagation conditions, network information, such as routing, for example, becomes quickly obsolete. This leads to frequent network reconfiguration and frequent exchanges of control information over the wireless medium. Of course, as the wireless spectrum is at premium, frequent exchanges of large amounts of data over the air should to be avoided. Moreover, because of the fast changing topology, a large portion of the reconfiguration information will never even be used. Thus, the bandwidth used for distribution of the routing update information is wasted. Finally, in spite of these attributes, the design of the ad-hoc networks still needs to allow for a high degree of reliability, survivability, availability and manageability of the network.
Based on the above discussion, the following features are considered as highly desirable for the successful operating of ad-hoc networks:
Routing Protocols
The routing protocols published in the literature are inadequate for the ad-hoc network communications environment. More specifically, the challenges stem from the fact that, on one hand, in-order to determine a packet route, at least the reachable information of the source's neighbors needs to be known to the source node. On the other hand, in an ad-hoc network, this topology may change quite often. Furthermore, as the number of network nodes can be large, the potential number of destinations is also large, requiring large and frequent exchange of data (e.g., routes, routes updates, or routing tables) among the network nodes. Thus, the amount of update traffic is quite high. This is in contradiction with the fact that updates are expensive in the wireless communication environment.
The existing routing protocols can be classified either as proactive or as reactive. Proactive protocols attempt to continuously evaluate the routes within the network, so that when a packet needs to be forwarded, the route is already known and can be immediately used. Reactive protocols, on the other hand, invoke a route determination procedure on demand only. Thus, when a route is needed, some sort of a global search procedure is employed.
The advantage of the proactive schemes is that, once a route is requested, there is little delay until a route is determined. In reactive protocols, because route information may not be available at the time a routing request is received, the delay to determine a route can be quite significant. Furthermore, the global search procedure of the reactive protocols requires significant control traffic. Because of this long delay and excessive control traffic, pure reactive routing protocols may not be applicable to real time communication. However, pure proactive schemes are likewise not appropriate for the ad-hoc network environment, as they continuously use a large portion of the network capacity to keep the routing information current. Since nodes in ad-hoc networks can move quite fast, and as the changes may be more frequent than the routing requests, most of this routing information is never even used! This results again in an excessive waste of the network capacity. What is needed is a protocol that, on one hand, initiates the route-determination procedure on-demand, but with limited cost of the global search.
A related issue is that of updates in the network topology. For a routing protocol to be efficient, changes in the network topology have to have local effect only. In other words, creation of a new link at one end of the network is an important local event but, most probably, not a significant piece of information at the other end of the network. Proactive protocols tend to distribute such topological changes widely in the network, incurring large costs.
Mobility Management
Traditionally, locating a user in a mobile system is performed by associating each user with a single entity in the network that keeps track at all times of the user's (sometimes approximate) location. Without restricting the discussion to a particular system, we will call this single entity a Home Location Registry (HLR). Tracking users is achieved through the registration process, in which every mobile user notifies its HLR about its current location within the network. Subsequent messages to the BIR indicating that the user had migrated into a new location are referred to as updates. The location update process can be based on different stimuli. Possible stimuli include the distance traveled by the mobile since the last update, time elapsed since the last update, or the migration of the user out of one and into another virtual area, referred to as Location Area-s (LA-s).
Location of a user can be tracked down exactly, known approximately, or not known at all In the first case, when a connection request or a message destined to the mobile arrives in the network, it can be immediately delivered to the mobile. Not so, however, in the second and the third cases, in which some amount of searching of the user is required to determine its location precisely. This searching is performed through the paging process. Paging is a process in which a query message asking the user to announce its location is broadcasted within the area of the user's location uncertainty. The queried user, on receipt of the query, sends an update message to the
Variants of this mobility management scheme are currently universally used in nearly every cellular system, from the mobile phone system, such as the AMPS and through the IP Mobility Support (a.k.a. Mobile IP) protocol of the Internet Engineering Task Force (IETF). Of course, the entities in different networks have different names, but the basic functions are the same. For example, the HLR is referred to as a Home Agent in the IETF Mobile-IP protocol and as a Mobile Home Function in the Cellular Digital Packet Data networks.
This mobility management scheme is, however, inadequate for ad-hoc networks, due to the fact that there is no single entity in the network that can keep track of the user's location. In other words, if a node were to assume the HLR function, there would be no assurance that such a node would be reachable or even present at any specific time. The culprit is in the fact that the traditional mobility management scheme relies, in fact, on a centralized approach.